﻿#include <iostream>
#include <assert.h>

#define STAR '*'
#define ANY '?'
#define IS_CHARACTER(c) (('a'<=c)&&('c'<='z'))
#define IS_ANY(c) (c==ANY)
#define IS_STAR(c) (c==STAR)

static bool isValid(const char* str, const char* exp)
{
	if (!str || !exp) return false;

	auto strLen = strlen(str);
	auto expLen = strlen(exp);
	char cur;

	for (int i = 0; i < strLen; i++)
	{
		cur = str[i];
		if (!IS_CHARACTER(cur))
		{
			return false;
		}
	}

	for (int i = 0; i < expLen; i++)
	{
		cur = exp[i];
		if (!IS_CHARACTER(cur) && !IS_STAR(cur) && !IS_ANY(cur))
		{
			return false;
		}

		if (i == 0 && IS_STAR(cur))
		{
			// 第0个字符不能是*
			return false;
		}

		if (i > 0 && IS_STAR(exp[i - 1]) && IS_STAR(cur))
		{
			// 不允许连在一起的*
			return false;
		}
	}

	return true;
}

/**
 * 暴力递归
 */
static bool process(const char* str, const size_t strLen, const char* exp, const size_t expLen, const int strIndex, const int expIndex)
{
	if (expIndex >= expLen)
	{
		// exp超出范围
		return strIndex >= strLen;
	}

	if (strIndex >= strLen)
	{
		// str超出范围
		if (expIndex >= expLen) return true;

		if (IS_STAR(exp[expIndex])) return false;

		if (expIndex + 1 < expLen)
		{
			if ((IS_CHARACTER(exp[expIndex]) || IS_ANY(exp[expIndex])) && IS_STAR(exp[expIndex + 1]))
			{
				return process(str, strLen, exp, expLen, strIndex, expIndex + 2);
			}
		}

		return false;
	}

	if (IS_STAR(exp[expIndex])) return false;

	if (expIndex + 1 >= expLen)
	{
		// exp在最后一个字符的位置上
		if (IS_ANY(exp[expIndex]) || exp[expIndex] == str[strIndex])
		{
			return process(str, strLen, exp, expLen, strIndex + 1, expIndex + 1);
		}
		else
		{
			return false;
		}
	}

	// 先不考虑'*'的情况
	if (!IS_STAR(exp[expIndex + 1]))
	{
		if (exp[expIndex] == str[strIndex] || IS_ANY(exp[expIndex]))
		{
			return process(str, strLen, exp, expLen, strIndex + 1, expIndex + 1);
		}
		else
		{
			return false;
		}
	}

	// 考虑'*'的情况
	bool res = false;
	int start = strIndex;

	// ?*
	if (IS_ANY(exp[expIndex]))
	{
		while (start < strLen)
		{
			res = process(str, strLen, exp, expLen, start + 1, expIndex);

			if (res) break;

			++start;
		}

		if (res) return true;
	}

	start = strIndex;
	while (str[start] == exp[expIndex])
	{
		res = process(str, strLen, exp, expLen, start + 1, expIndex + 2);
		if (res) break;

		++start;
	}

	if (res) return true;

	// 忽略exp一个字母+'*'，查看str当前位置是否能匹配exp之后的
	return process(str, strLen, exp, expLen, strIndex, expIndex + 2);
}

static void printDp(const bool* dp, const size_t expLen, const size_t strLen)
{
	int xSize = strLen + 1;
	for (int expIndex = 0; expIndex <= expLen; expIndex++)
	{
		for (int strIndex = 0; strIndex <= strLen; strIndex++)
		{
			printf("%d ", dp[strIndex + expIndex * xSize]);
		}

		printf("\n");
	}
}

/**
 * 动态规划
 */
static bool isMatchedDp(const char* str, const char* exp)
{
	auto strLen = strlen(str);
	auto expLen = strlen(exp);
	int xSize = strLen + 1;
	bool* dp = (bool*)malloc((strLen + 1) * (expLen + 1) * sizeof(bool));
	memset(dp, 0, (strLen + 1) * (expLen + 1) * sizeof(bool));

	for (int strIndex = 0; strIndex <= strLen; strIndex++)
	{
		dp[strIndex + expLen * xSize] = (strIndex >= strLen);
	}

	for (int expIndex = expLen - 1; expIndex >= 0; expIndex--)
	{
		int strIndex = strLen;
		if (expIndex >= expLen)
		{
			dp[strIndex + expIndex * xSize] = true;
			continue;
		}
		
		if (IS_STAR(exp[expIndex]))
		{
			dp[strIndex + expIndex * xSize] = false;
			continue;
		}

		if (expIndex + 1 < expLen)
		{
			if ((IS_CHARACTER(exp[expIndex]) || IS_ANY(exp[expIndex])) && IS_STAR(exp[expIndex + 1]))
			{
				dp[strIndex + expIndex * xSize] = dp[strIndex + (expIndex + 2) * xSize];
				continue;
			}
		}

		dp[strIndex + expIndex * xSize] = false;
	}

	for (int strIndex = strLen - 1; strIndex >= 0; strIndex--)
	{
		int expIndex = expLen - 1;
		if (IS_STAR(exp[expIndex]))
		{
			dp[strIndex + expIndex * xSize] = false;
			continue;
		}

		if (IS_ANY(exp[expIndex]) || exp[expIndex] == str[strIndex])
		{
			dp[strIndex + expIndex * xSize] = dp[(strIndex + 1) + (expIndex + 1) * xSize];
		}
		else
		{
			dp[strIndex + expIndex * xSize] = false;
		}
	}

	bool res;
	int start;
	for (int strIndex = strLen - 1; strIndex >= 0; strIndex--)
	{
		for (int expIndex = expLen - 2; expIndex >= 0; expIndex--)
		{
			if (IS_STAR(exp[expIndex]))
			{
				dp[strIndex + expIndex * xSize] = false;
				continue;
			}

			// 先不考虑'*'的情况
			if (!IS_STAR(exp[expIndex + 1]))
			{
				if (exp[expIndex] == str[strIndex] || IS_ANY(exp[expIndex]))
				{
					dp[strIndex + expIndex * xSize] = dp[strIndex + 1 + (expIndex + 1) * xSize];
				}
				else
				{
					dp[strIndex + expIndex * xSize] = false;
				}

				continue;
			}

			// 考虑'*'的情况
			res = false;
			start = strIndex;

			// ?*
			if (IS_ANY(exp[expIndex]))
			{
				while (start < strLen)
				{
					res = dp[start + 1 + expIndex * xSize];

					if (res) break;

					++start;
				}

				if (res) dp[strIndex + expIndex * xSize] = true;
			}

			start = strIndex;
			while (str[start] == exp[expIndex])
			{
				res = process(str, strLen, exp, expLen, start + 1, expIndex + 2);
				res = dp[start + 1 + (expIndex + 2) * xSize];
				if (res) break;

				++start;
			}

			if (res)
			{
				dp[strIndex + expIndex * xSize] = true;
				continue;
			}

			assert(expIndex + 2 <= expLen);
			dp[strIndex + expIndex * xSize] = dp[strIndex + (expIndex + 2) * xSize];
		}
	}

	//printDp(dp, expLen, strLen);

	res = dp[0];
	free(dp);
	return res;
}

/**
 * 判定一个由'a'-'z'字符构成的字符串和一个包含'?'和'*'通配符的字符串是否匹配。
 * 通配符'?'匹配任意单一字符，'*'匹配任意多个字符包括0个字符。
 * 字符串长度不会超过100，字符串不为空。
 * 输入描述:
 * 字符串str和包含通配符的字符串pattern. 1≤字符串长度≤100
 * 输出描述：
 * true表示匹配，false表示不匹配
 * 
 * 思路:
 * 设原字符串是str，含有通配符的字符串是exp.
 * exp中除了'a'-'z'之外，还包括'?'和'*'.
 * '?'可以匹配'a'-'z'任意一个字符，但是只能匹配一个。
 * '*'无法单独使用，必须跟在'a'-'z'或者'?'之后, 比如, "a*"可以表示有0个a或者任意多个a.
 * 
 * 举例:
 * 1. 当str="abcd"时, exp="a*bcd", exp也可以="?*"("?*"可以匹配任意str)
 * 2. 当str="abcde"时，exp="abc*de"是可以的，但是exp="abc*e"就不行，因为无法表示'd'
 * 
 * 暴力递归：
 * 看str从位置i到str.Length-1能否与exp从位置j到exp.Length-1相匹配.
 * 假设str[i]=='a'
 * 情况1: exp[j+1]≠'*', 那么exp[j]=='a'或者exp[j]=='?'能匹配, 否则不能匹配
 * 情况2: exp[j+1]=='*', 那么要看str[i]是否等于exp[j], 又或者exp[j]=='?'. 这种情况还需要考虑，一个非*字符加一个*，也可以匹配0个字符，故也需要跳过它们看exp的后续匹配情况。 
 * 
 * 动态规划:
 * 
 *      str:    a   b   c   d   e  end
 *              0   1   2   3   4   5   startIndex
 * ------------------------------------------
 * exp: a   0|                  0   0         
 *      a   1|                  0   0        
 *      *   2|  0   0   0   0   0   0        
 *      b   3|                  0   0          
 *      c   4|                  0   0            
 *      d   5|                  0   0             
 *      e   6|                  1   0        
 *     end  7|  0   0   0   0   0   1           
 *       expIndex
 *        
 * 填写宗旨是：严格按照暴力递归的逻辑推导。
 * 
 * 先根据边界条件，将expIndex==7的值填好。
 * startIndex==5时，需要根据expIndex从高到低递推。
 * 对于普遍位置，根据暴力递归的逻辑，(startIndex,expIndex)可能和(startIndex+1,expIndex+1),(startIndex+1,expIndex),(startIndex+2,expIndex),...(startIndex+n,expIndex),(startIndex,expIndex+2),(startIndex+1,expIndex+2),(startIndex+2,expIndex+2),...,(startIndex+n,expIndex+2)有关
 */
int main_wildcardCharacter()
{
#define MAX_CHAR_COUNT 101
	char strs[][MAX_CHAR_COUNT] =
	{
		"a",
		"",
		"abcde",
		"abcde",
		"abcde",
		"abcde",
		"abcde",
		"aaaaab",
		"aaaaab",
		"aaaaab",
		"aaaaab",
	};

	char exps[][MAX_CHAR_COUNT] = 
	{
		"*a",
		"",
		"a*e*fbcde",
		"aa*bcde",
		"a*abcde",
		"aa*?b*cd?",
		"?*cde",
		"?*",
		"aaaaa*b*",
		"aaa*bb*",
		"?*?*bbb*",
	};

	size_t count = sizeof(strs) / MAX_CHAR_COUNT;
	bool valid;
	bool isMatched;
	bool useDp;
	for (int i = 0; i < count; i++)
	{
		valid = isValid(strs[i], exps[i]);
		if (!valid)
		{
			printf("ori:\"%s\" exp:\"%s\" not valid!\n", strs[i], exps[i]);
			continue;
		}

		isMatched = process(strs[i], strlen(strs[i]), exps[i], strlen(exps[i]), 0, 0);

		/*	int expLen = strlen(exps[i]);
			int strLen = strlen(strs[i]);
			int xSize = strLen + 1;
			for (int expIndex = 0; expIndex <= expLen; expIndex++)
			{
				for (int strIndex = 0; strIndex <= strLen; strIndex++)
				{
					printf("%d ", process(strs[i], strlen(strs[i]), exps[i], strlen(exps[i]), strIndex, expIndex));
				}

				printf("*****\n");
			}*/

		useDp = isMatchedDp(strs[i], exps[i]);
		printf("ori:\"%s\" exp:\"%s\" isMatched:%d dp:%d\n", strs[i], exps[i], isMatched, useDp);
	}

	return 0;
}